Bộ sinh Fibonacci trễ

Bộ sinh Fibonacci trễ (tiếng anh: Lagged Fibonacci Generator, hay gọi tắt đi là LFG hoặc đôi khi là LFib) là ví dụ của bộ sinh số giả ngẫu nhiên. Lớp các bộ sinh số giả ngẫu nhiên dựa trên dạng tổng quát của dãy Fibonacci.Dãy fibonacci được mô tả theo liên hệ lặp lại sau:Trong đó mỗi phần tử mới là tổng của hai phần tử cuối trong dãy. Ta tổng quát công thức trên thành như sau:Trong đó, trong đó phần tử mới là hợp của hai phần tử trước đó trong dãy. Giá trị m thường là lũy thừa của 2 (m = 2M), thường lấy giá trị 232 hoặc 264. Phép toán ⋆ {\displaystyle \star } ký hiệu phép toán hai ngôi nói chung. Phép toán này có thể là phép cộng, phép trừ, phép nhân hoặc phép toán thao tác từng bit (XOR). Lý thuyết của các bộ sinh số này có thể rất phức tạp và không chỉ đơn giản là chọn bừa các giá trị cho j và k. Các bộ sinh số ngẫu nhiên này cũng rất nhậy cảm với các giá trị và phép toán khởi tạo.Các bộ sinh số giả ngẫu nhiên dạng này sẽ lưu k trạng thái (tức là nó có thể nhớ k giá trị cuối).Nếu phép toán được dùng là phép cộng, thì bộ sinh được gọi là Bộ sinh Fibonacci trễ cộng tính hoặc ALFG, nếu phép nhân được dùng thì nó được gọi là, Bộ sinh Fibonacci trễ nhân tính hoặc MLFG, còn nếu phép XOR được dùng thì bộ sinh được gọi là thanh ghi dịch phản hồi tổng quát hai số hoặc GFSR. Thuật toán Mersenne Twister là dạng khác của GFSR. GFSR thường liên hệ với thanh ghi dịch phản hồi tuyến tính, hoặc LFSR.